//
// Created by Administrator on 2021/5/25.
//

#include <iostream>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


class Solution {
    // 树上节点的值都互不相同
private:
    TreeNode *ansNode;
public:
    TreeNode *getTargetCopy(TreeNode *original, TreeNode *cloned, TreeNode *target) {
        dfs(cloned, target);
        return ansNode;
    }

    void dfs(TreeNode *root, TreeNode *target) {
        if (root == nullptr) return;
        dfs(root->left, target);
        if (root->val == target->val) {
            ansNode = root;
            return;
        }
        dfs(root->right, target);
    }

    TreeNode *getTargetCopy2(TreeNode *original, TreeNode *cloned, TreeNode *target) {
        //递归结束条件：遍历到树末端
        if (original == nullptr) return nullptr;
        //找到目标节点，返回对应节点
        if (original == target) return cloned; // 唯一的精髓在这里
        //递归在左右子树中搜索，并返回
        auto res = getTargetCopy2(original->left, cloned->left, target);
        return res == nullptr ? getTargetCopy2(original->right, cloned->right, target) : res;
    }
};

int main() {
    auto n1 = TreeNode(7), n2 = TreeNode(4), n3 = TreeNode(3), n4 = TreeNode(6), n5 = TreeNode(19);
    n1.left = &n2;
    n1.right = &n3;
    n3.left = &n4;
    n3.right = &n5;

    Solution sol{};
    auto ans = sol.getTargetCopy2(&n1, &n1, &n3);
    cout << ans->val << endl;
    return 0;
}